package com.yaoli.niuke;

/**
 * Created by will on 2017/5/4.
 */
public class _002_Test {
    public static void main(String[] args) {
        _002_Test test = new _002_Test();
        int nums [] = {1, 4, 3, 6, 8, 1, 5};
        System.out.println(test.VerifySquenceOfBST(nums));
    }

    public boolean VerifySquenceOfBST(int [] sequence) {


        if(sequence.length == 0) {
            return false;
        }else{
            if(sequence.length == 1 || sequence.length == 2){
                return true;
            }else{
                Integer seq []= new Integer[sequence.length];
                for(int i = 0 ; i < sequence.length ; i++){
                    seq[i] = sequence[i];
                }
                Integer set [] = get(seq,sequence.length - 1, 0 , sequence.length - 2);
                return calc(seq,sequence.length - 1,set[0],set[1],set[2],set[3]);
            }
        }
    }

    public boolean calc(Integer [] seq,Integer root,Integer ll,Integer lr,Integer rl,Integer rr){

        boolean rightOk = true;
        boolean leftOk = true;

        if(ll == null && lr == null){
            leftOk = true;
        }else{
            //检查左子树
            for(int i = ll ; i <= lr ; i++){
                if(seq[i] > seq[root]){
                    leftOk = false;
                    break;
                }
            }

            if(leftOk != false){
                Integer [] leftp = get(seq,lr,ll,lr - 1);
                rightOk = calc(seq,lr,leftp[0],leftp[1],leftp[2],leftp[3]);
            }
        }


        if(rl == null && rr == null){
            rightOk = true;
        }else{
            //检查右子树
            for(int i = rl; i <= rr ; i++){
                if(seq[i] < seq[root]){
                    rightOk = false;
                    break;
                }
            }

            if(rightOk != false){
                Integer [] rightp = get(seq,rr,rl,rr - 1);
                rightOk = calc(seq,rr,rightp[0],rightp[1],rightp[2],rightp[3]);
            }
        }


        if(rightOk == true && leftOk == true){
            return true;
        }else{
            return false;
        }
    }

    public Integer [] get(Integer [] seq ,int root, int l , int r){
        Integer res [] = new Integer[4];

        if(l > r){
            return res;
        }

        Integer ll = null;
        Integer lr = null;
        Integer rl = null;
        Integer rr = null;

        for(int i = r; i >= l ; i--){
            if(seq[i] > seq[root] && rr == null){
                rr = i;
            }

            if(seq[i] < seq[root] && lr == null){
                lr = i;
                break;
            }
        }


        if(lr != null){
            if(rr != null){
                rl = lr + 1;
            }
            ll = l;
        }else{
            if(rr != null){
                rl = l;
            }
        }

        res[0] = ll;
        res[1] = lr;
        res[2] = rl;
        res[3] = rr;

        return res;

    }
}
